#ifndef _NOLOCK_H_
#define _NOLOCK_H_

// a non-locking hash table for use with threaded functions
#include "util.h"
#include "jobqueue.h"

// the key is always a uint64
//   0 is not a valid key. 
template<class Value> 
struct NLHash {
  struct Entry {
    uint64 key_;
    Value value_;
  };
  NLHash() {}
  NLHash(uint64 lg_size, bool zero_out = true) {
    Init(lg_size, zero_out);
  }
  void Init(uint64 lg_size, bool zero_out) {
    size_ = 1 << lg_size;
    CHECK(size_);
    mod_mask_ = size_ - 1;
    data_ = new Entry[size_];
    if (zero_out) // this doesn't really templatize. 
      for (uint64 i=0; i<size_; i++) {
	data_[i].key_ = 0;
	data_[i].value_ = Value();
      }
    max_look_ = 0;
  }
  Value * Lookup(uint64 key, bool insert = false) {
    uint64 pos = key & mod_mask_;
    uint64 step = 0;
    while(1) {
      uint64 k = data_[pos].key_;
      if (k == key) {
	// matched the key
	return &(data_[pos].value_);
      }
      if (k == 0) {
	if (!insert) return NULL;
	bool success = __sync_bool_compare_and_swap(&data_[pos].key_, 0, key);
	if (success) return &(data_[pos].value_);
	// CHECK(data_[pos].key_);
	if (data_[pos].key_ == key) return &(data_[pos].value_);
      }
      pos = (pos + (++step)) & mod_mask_;
      if (step > max_look_) max_look_ = step;
      continue;      
    }    
  }
  Value * InsertOrReturn(uint64 key) { return Lookup(key, true); }

  Value LookupOrDefault(uint64 key, const Value & default_value) {
    Value * look = Lookup(key, false);
    if (look) return *look; 
    return default_value;
  } 

  void JQZero(JobQueue * jq) {
    JobQueueZero(jq, data_, size_ * sizeof(Entry));
    max_look_ = 0;
  }

  // for linear iteration
  uint64 Size() const { return size_; }
  uint64 & KeyRef(uint64 n) { return data_[n].key_;}
  Value & ValueRef(uint64 n) { return data_[n].value_;}
  
  void Store(ostream * output) {
    Write(output, size_);
    WriteSizePrefixed(output, (const char *)data_, size_ * sizeof(Entry));
  }
  void Load(const char ** p) {
    Read(p, &size_);
    data_ = (Entry *)ReadSizePrefixed(p);
    mod_mask_ = size_ - 1;
    max_look_ = 0;
  }

  Entry *data_;
  uint64 size_;
  uint64 mod_mask_;
  uint64 max_look_;
};

// thread-safe non-locking cache of a function from uint64 to uint64.  
struct NLCache {
  // a cell in the execution cache
  struct Cell {
    uint64 kvs_;    // derived from the key, the value, and the signature.
    uint64 value_;   // the return value
  };

  Cell *data_; // the execution cache
  uint64 size_;   // in cache cells. better be a power of 2. 
  uint64 mask_;   // size-1
  // a random number.  Change it to clear the cache. 
  uint64 signature_;
  uint64 lookups_;
  uint64 stores_;

  NLCache(int64 size) {
    CHECK((size & (size-1)) == 0);
    size_ = size;
    mask_ = size_ - 1;
    lookups_ = 0;
    stores_ = 0;
    CHECK(!(size_ & mask_));
    data_ = new Cell[size];
    Clear();
  }
  void Clear() { 
    uint64 old_signature = signature_;
    while (1) {
      signature_ = rand(); 
      if (signature_ != old_signature) break;
    }
    // cout << "lookups: " << lookups_ << endl;
    // cout << "stores: " << stores_ << endl;
    lookups_ = 0;
    stores_ = 0;
  }
  
  ~NLCache() {
    delete [] data_;
  }
  void Store(uint64 k, uint64 v) {
    // stores_++;
    Cell & c_ref = data_[Fingerprint(k, signature_) & mask_];
    c_ref.kvs_ = k + v + signature_;
    c_ref.value_ = v;
  }
  bool Lookup(uint64 k, uint64 * result) {
    // lookups_++;
    Cell c = data_[Fingerprint(k, signature_) & mask_];
    if (c.kvs_ != k + c.value_ + signature_) return false;
    *result = c.value_;
    return true;
  } 
};

// non-thread-safe cache.
struct SimpleCache {
  // a cell in the execution cache
  struct Cell {
    uint64 generation_;
    uint64 key_;
    uint64 value_;
  };

  Cell *data_; // the execution cache
  uint64 size_;   // in cache cells. better be a power of 2. 
  uint64 mask_;   // size-1

  // a random number.  Change it to clear the cache. 
  uint64 generation_;

  SimpleCache(int64 size) {
    size_ = size;
    mask_ = size_ - 1;
    CHECK(!(size_ & mask_));
    data_ = new Cell[size];
    for (uint64 i=0; i<size_; i++) data_[i].generation_ = 0;
    generation_ = 1;
  }
  void Clear() { generation_++; }
  
  ~SimpleCache() { delete [] data_; }

  void Store(uint64 k, uint64 v) {
    // stores_++;
    Cell & c_ref = data_[k & mask_];
    c_ref.key_ = k;
    c_ref.value_ = v;
    c_ref.generation_ = generation_;
  }
  bool Lookup(uint64 k, uint64 * result) {
    // lookups_++;
    Cell c = data_[k & mask_];
    if (c.generation_ != generation_) return false;
    if (k != c.key_) return false;
    *result = c.value_;
    return true;
  }
};




#endif
